package com.javabasic.algorithm.sword_of_offer;

/**
 * @Author xiongmin
 * @ClassName 重建二叉树
 * @Description TODO
 * @Date 2019/9/7 22:52
 * @Version 1.0
 **/
public class 重建二叉树 {

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode treeNode = null;
        return dfs(pre,0,pre.length-1,in,0,in.length-1,treeNode);
    }

    private TreeNode dfs(int[] pre, int preLeft, int preRight, int[] in, int inLeft, int inRight,TreeNode treeNode) {

        if (preLeft <= preRight) {
            int root = pre[preLeft];
            int tempLen = 0;
            for (int i = inLeft; i <= inRight; i++) {
                if (in[i] == root) {
                    tempLen = i-inLeft;
                    break;
                }
            }
            treeNode = new TreeNode(root);
            treeNode.left  = dfs(pre,preLeft+1,preLeft+tempLen,in,inLeft,inLeft+tempLen-1,treeNode);
            treeNode.right = dfs(pre,preLeft+tempLen+1,preRight,in,inLeft+tempLen+1,inRight,treeNode);
            return treeNode;
        } else {
            return null;
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}